package tree.binarysearchtree;

import tree.TreeNode;

/**
 * @Classname : BinarySearchTree
 * @Description : 二叉搜索树 Binary Search Tree, BST
 * 定义：BST是一种特殊的二叉树，对于每个父节点，其左子树中所有节点的值小于等于父结点的值，其右子树中所有节点的值大于等于父结点的值。
 * 优点：
 * ① 可以在 O(log n) 的时间内查找一个值是否存在：从根节点开始，若当前节点的值大于查找值则向左下走，若当前节点的值小于查找值则向右下走。
 * ② 可以在 O(log n) 的时间内查找最大值和最小值。
 * ③ 中序遍历的结果即为由小到大排好序的数组。
 *
 * @Author : chentianyu
 * @Date 2023/1/8 21:39
 */


public class BinarySearchTree {

    public static void main(String[] args) {
        BinarySearchTree BST = new BinarySearchTree();
        System.out.println("【插入】BST 依次插入 3、1、5、4、2");
        BST.insert(3);
        BST.insert(1);
        BST.insert(5);
        BST.insert(4);
        BST.insert(2);
        System.out.println("【查询】当前最大值为：" + BST.findMax().val);
        System.out.println("【查询】当前最小值为：" + BST.findMin().val);
        System.out.println("【删除】BST 依次删除 5、1");
        BST.remove(5);
        BST.remove(1);
        System.out.println("【查询】当前最大值为：" + BST.findMax().val);
        System.out.println("【查询】当前最小值为：" + BST.findMin().val);

        /** 20230108
         * 【插入】BST 依次插入 3、1、5、4、2
         * 【查询】当前最大值为：5
         * 【查询】当前最小值为：1
         * 【删除】BST 依次删除 5、1
         * 【查询】当前最大值为：4
         * 【查询】当前最小值为：2
         */
    }

    TreeNode root;

    /**
     * 插入
     *
     * @param x
     */
    public void insert(Integer x) {
        root = insert(root, x);
    }

    private TreeNode insert(TreeNode t, Integer x) {
        if (t == null)  t = new TreeNode(x);
        else if (x < t.val) t.left = insert(t.left, x);
        else t.right = insert(t.right, x);
        return t;
    }


    /**
     * 查找
     *
     * @param x
     * @return
     */
    public TreeNode find(Integer x) {
        return find(root, x);
    }

    private TreeNode find(TreeNode t, Integer x) {
        if (t == null) return null;

        if (x < t.val) return find(t.left, x);
        if (x > t.val) return find(t.right, x);
        return t;
    }


    /**
     * 查找最小值
     *
     * @return
     */
    public TreeNode findMin() {
        return findMin(root);
    }

    private TreeNode findMin(TreeNode t) {
        if (t == null || t.left == null) return t;
        return findMin(t.left);
    }


    /**
     * 查找最大值
     *
     * @return
     */
    public TreeNode findMax() {
        return findMax(root);
    }

    private TreeNode findMax(TreeNode t) {
        if (t == null || t.right == null) return t;
        return findMax(t.right);
    }


    /**
     * 删除
     *
     * @param x
     * @return
     */
    public void remove(Integer x) {
        remove(root, x);
    }

    private TreeNode remove(TreeNode t, Integer x) {
        if (t == null) return null;

        if (x < t.val) t.left = remove(t.left, x);
        else if (x > t.val) t.right = remove(t.right, x);
        else if (t.left != null && t.right != null) {
            TreeNode rightMin = findMin(t.right);
            t.val = rightMin.val;
            t.right = remove(t.right, t.val);  // 当右子树只有一个节点时，将右子节点赋值为null
        } else {
            if (t.left != null) t = t.left;
            else t = t.right;
        }
        return t;
    }
}
